struct Trie { // 字典树

enum{TRIE_WIDTH = 10};

// 编码
template<typename T>

int _tr(T t){ 
    assert(0);
}

void init(int sz = 10000){
	toUsed = 0;
	dfa.clear();
	dfa.reserve(sz);
	dfa.push_back({0});
	dfa.push_back({0});
	ErrorState = 0;
	StartState = 1;
}

/// 插入
template<typename IT>
void insert(IT s, IT e, int idx = 0){
    int st = StartState;
	for(auto it=s;it!=e;++it){
        int sn = _tr(*it);
		if(0 == dfa[state][sn]) {
			dfa[state][sn] = dfa.size();
			dfa.push_back({0});
		}
		state = dfa[state][sn];
	}
	// label[state] = idx;
	return;
}


/// 自动机
vector<array<int, TRIE_WIDTH>> dfa;
int toUsed;

int ErrorState;
int StartState;

vector<int> label;

};